#ifndef POLY_H
#define POLY_H

#include "frac.h"
#include <algorithm>
#include <iostream>
#include <vector>
#include <sstream>

class poly {
public:
    poly(const std::vector<Frac>& coeffs)
        : coef(coeffs)
    {
        trim();
    }

    poly operator+(const poly& rhs) const
    {
        std::vector<Frac> result(std::max(coef.size(), rhs.coef.size()), Frac(0));
        for (size_t i = 0; i < coef.size(); ++i)
            result[i] = result[i] + coef[i];
        for (size_t i = 0; i < rhs.coef.size(); ++i)
            result[i] = result[i] + rhs.coef[i];
        return poly(result);
    }

    poly operator-(const poly& rhs) const
    {
        std::vector<Frac> result(std::max(coef.size(), rhs.coef.size()), Frac(0));
        for (size_t i = 0; i < coef.size(); ++i)
            result[i] = result[i] + coef[i];
        for (size_t i = 0; i < rhs.coef.size(); ++i)
            result[i] = result[i] - rhs.coef[i];
        return poly(result);
    }

    poly operator*(const poly& rhs) const
    {
        std::vector<Frac> result(coef.size() + rhs.coef.size() - 1, Frac(0));
        for (size_t i = 0; i < coef.size(); ++i)
            for (size_t j = 0; j < rhs.coef.size(); ++j)
                result[i + j] = result[i + j] + coef[i] * rhs.coef[j];
        return poly(result);
    }

    std::string to_string(const std::string& var = "x") const
    {
        std::ostringstream oss;
        oss << *this;
        return oss.str();
    }

    friend std::ostream& operator<<(std::ostream& os, const poly& p)
    {
        bool first = true;
        for (int i = p.coef.size() - 1; i >= 0; --i) {
            if (p.coef[i].isZero())
                continue;
            if (!first && p.coef[i].sign() > 0)
                os << " + ";
            if (p.coef[i].sign() < 0)
                os << " - ";
            Frac absCoef = p.coef[i].abs();
            if (!absCoef.isOne() || i == 0)
                os << absCoef;
            else if (i != 0 && absCoef.isOne())
                ; // 系数为1且不是常数项，不输出数字
            if (i > 0)
                os << "x";
            if (i > 1)
                os << "^" << i;
            first = false;
        }
        if (first)
            os << "0";
        return os;
    }

private:
    std::vector<Frac> coef;
    void trim()
    {
        while (!coef.empty() && coef.back().isZero())
            coef.pop_back();
        if (coef.empty())
            coef.push_back(Frac(0));
    }
};

#endif